package problem4;

public class Main {
    public static void main(String[] args) {
       int[] arr1 = {1, 3, 5, 7, 9};
       int[] arr2 = {2, 4, 6, 8, 10, 12};
       int k = 1;
       int ret = findKNum(arr1, arr2, k);
        System.out.println(ret);

    }
    public static int findKNum(int[] arr1, int[] arr2, int k) {
        int l1 = arr1.length, l2 = arr2.length;
        //保证arr1是长度较短的数组
        if(l1 < l2) return findKNum(arr2, arr1, k);
        int start1 = 0, start2 = 0;
        while(k > 1) {
            if(start1 == l1) {
                return arr2[start2 + k - 1];
            }
            int i = Math.min(k/2, l1 - start1);
            int j = Math.min(k/2, l2 - start2);
            if(arr1[start1 + i - 1] < arr2[start2 + j -1]) {
                k-=i;
                start1 += i;
            }else {
                k -= j;
                start2 += j;
            }
        }
        if(start1 == l1) {
            return arr2[start2];
        }
        if(start2 == l2) {
            return arr1[start1];
        }
        return Math.min(arr1[start1], arr2[start2]);
    }
}